{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 8: Hashing!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from random import choice\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First let's implement a (chained) hash table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable:\n",
    "    # init function for our hash table\n",
    "    # h is a function that maps a universe U to range(n)\n",
    "    def __init__(self, h, n):\n",
    "        self.h = h\n",
    "        # store n buckets, each of which has a linked list. \n",
    "        # I'm just going to implement as python arrays.\n",
    "        self.buckets = [ [] for i in range(n) ]\n",
    "        \n",
    "    def insert(self, x):\n",
    "        self.buckets[self.h(x)].append(x)\n",
    "        \n",
    "    # delete an item in the hash table, if it's in there\n",
    "    # returns the deleted item, or None if it wasn't found.\n",
    "    def delete(self,x):\n",
    "        bucket = self.buckets[self.h(x)]\n",
    "        # take time O(n) to look for x in the bucket.\n",
    "        for i in range(len(bucket)):\n",
    "            if bucket[i] == x:\n",
    "                return bucket.pop(i)\n",
    "        return None\n",
    "    \n",
    "    # same as delete, but don't remove it when you find it.\n",
    "    def find(self,x):\n",
    "        bucket = self.buckets[self.h(x)]\n",
    "        # take time O(n) to look for x in the bucket.\n",
    "        for i in range(len(bucket)):\n",
    "            if bucket[i] == x:\n",
    "                return bucket[i]  \n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Let's define a few of our favorite hash functions.  \n",
    "\n",
    "### Here's the \"last digit\" hash function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def xModn(x,n=10):\n",
    "    return x%n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "print(xModn(52))\n",
    "print(xModn(3235235))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Does this work?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "successfully found 1234567 : GREAT!\n",
      "76554334234 is not in the hash table : GREAT!\n"
     ]
    }
   ],
   "source": [
    "HT = HashTable(xModn, 10) # make a hash table that uses the last digit.\n",
    "\n",
    "x = 1234567\n",
    "y = 76554334234\n",
    "HT.insert(x)\n",
    "\n",
    "# let's make sure that x is there and y isn't.\n",
    "if HT.find(x) == x:\n",
    "    print(\"successfully found\", x, \": GREAT!\")\n",
    "else:\n",
    "    print(\"failed to find\", x, \": SOMETHING's BROKEN!\")\n",
    "    \n",
    "    \n",
    "if HT.find(y) == None:\n",
    "    print( y, \"is not in the hash table\", \": GREAT!\")\n",
    "else:\n",
    "    print( \"found\", y, \"in the hash table\", \": SOMETHING's BROKEN!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How about a uniformly random hash function?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "def randomFn(x, n=10):\n",
    "    return choice(range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "print(randomFn(52))\n",
    "print(randomFn(3235235))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's make sure that works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "failed to find 1234567 : SOMETHING's BROKEN!\n",
      "76554334234 is not in the hash table : GREAT!\n"
     ]
    }
   ],
   "source": [
    "HT = HashTable(randomFn, 10) # make a hash table that uses the last digit.\n",
    "\n",
    "x = 1234567\n",
    "y = 76554334234\n",
    "HT.insert(x)\n",
    "\n",
    "# let's make sure that x is there and y isn't.\n",
    "if HT.find(x) == x:\n",
    "    print(\"successfully found\", x, \": GREAT!\")\n",
    "else:\n",
    "    print(\"failed to find\", x, \": SOMETHING's BROKEN!\")\n",
    "    \n",
    "    \n",
    "if HT.find(y) == None:\n",
    "    print( y, \"is not in the hash table\", \": GREAT!\")\n",
    "else:\n",
    "    print( \"found\", y, \"in the hash table\", \": SOMETHING's BROKEN!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Whoops!  \n",
    "\n",
    "### What went wrong?\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "(Think about it)\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "(Still thinking)\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "## The problem is that this isn't a function! \n",
    "It takes different values different times it's called.\n",
    "So we can't use it to look up a stored element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "print(randomFn(52))\n",
    "print(randomFn(3235235))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(randomFn(52))\n",
    "print(randomFn(3235235))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In order to make it a function, we need to keep track of all of the values!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# generate a uniformly random hash function from range(M) to range(n).\n",
    "def generateUniformlyRandomHashFunction(M, n=10):\n",
    "    fnTable = [ None for i in range(M) ]\n",
    "    for x in range(M):\n",
    "        fnTable[x] = choice(range(n))\n",
    "    def randomFn(x):\n",
    "        return fnTable[x]\n",
    "    return randomFn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try this again..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "randomFnTake2 = generateUniformlyRandomHashFunction(1000, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(randomFnTake2(52))\n",
    "print(randomFnTake2(324))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(randomFnTake2(52))\n",
    "print(randomFnTake2(324))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "successfully found 123 : GREAT!\n",
      "76 is not in the hash table : GREAT!\n"
     ]
    }
   ],
   "source": [
    "HT = HashTable(randomFnTake2, 10) # make a hash table that uses the last digit.\n",
    "\n",
    "x = 123\n",
    "y = 76\n",
    "HT.insert(x)\n",
    "\n",
    "# let's make sure that x is there and y isn't.\n",
    "if HT.find(x) == x:\n",
    "    print(\"successfully found\", x, \": GREAT!\")\n",
    "else:\n",
    "    print(\"failed to find\", x, \": SOMETHING's BROKEN!\")\n",
    "    \n",
    "    \n",
    "if HT.find(y) == None:\n",
    "    print( y, \"is not in the hash table\", \": GREAT!\")\n",
    "else:\n",
    "    print( \"found\", y, \"in the hash table\", \": SOMETHING's BROKEN!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's the problem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say that I wanted to hash all possible twitter hashtags.  (A hashtag is allowed to be as long as a tweet -- 140 characters).  There are 128 ASCII symbols, so the number of possible hashtags is (128)^(140)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "randomFnForHashtags = generateUniformlyRandomHashFunction(128**140, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Universal Hash Families\n",
    "\n",
    "For a completely random hash function, we chose a function at random from the set {all of the functions}\n",
    "\n",
    "Instead, we could choose a function at random from a smaller set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Not a good hash family\n",
    "\n",
    "Here's the example from the slides"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "def leastSigDig(x,n=10):\n",
    "    return x%n\n",
    "\n",
    "def mostSigDig(x,n=10):\n",
    "    if x == 0:\n",
    "        return 0\n",
    "    while x > 0:\n",
    "        last = x%n\n",
    "        x = (x/n).__trunc__()\n",
    "    return last\n",
    "\n",
    "# our hash family will be { leastSigDig, mostSigDig }\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A better hash family\n",
    "\n",
    "This is the universal hash family we saw in class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "def generateUniversalHashFn(a,b,p,n=10):\n",
    "    # now define f.\n",
    "    def f(x):\n",
    "        r = (a*x + b) % p\n",
    "        return r % n\n",
    "    return f        \n",
    "\n",
    "# our hash family is the set { generateUniversalHAshFn(a,b,p) : a=1,..,p-1, b=0,...,p-1 }\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's compare collision probabilities!\n",
    "\n",
    "Small collision probability is good, it means the buckets of our hash table never get too full."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# Estimates collision probabilities\n",
    "# hashFamilyFn is a method that returns a function at random from a hash family\n",
    "# M is the size of the universe\n",
    "def getCollisionProbabilities(hashFamilyFn, M, trials=100):\n",
    "    data = []\n",
    "    for x in range(M):\n",
    "        for y in range(x+1, M):\n",
    "            countxy = 0\n",
    "            # let's estimate collision probability\n",
    "            for t in range(trials):\n",
    "                h = hashFamilyFn() # draw a random hash function\n",
    "                if h(x) == h(y):\n",
    "                    countxy += 1\n",
    "            data.append(countxy/trials)\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# Let's hash 100 things into 10 buckets.\n",
    "M = 100\n",
    "n = 10\n",
    "p = 101 # this is the smallest prime larger than 100\n",
    "\n",
    "# here are our hash families\n",
    "def drawFromBadHashFamily():\n",
    "    return choice( [ leastSigDig, mostSigDig ] )\n",
    "\n",
    "def drawFromGoodHashFamily():\n",
    "    a = choice( range(1, p))\n",
    "    b = choice(range(p))\n",
    "    return generateUniversalHashFn(a,b,p)\n",
    "\n",
    "# this is the benchmark, although the storage is prohibitive:\n",
    "def drawFromBestHashFamily():\n",
    "    return generateUniformlyRandomHashFunction(M,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# get some data\n",
    "dataBad = getCollisionProbabilities(drawFromBadHashFamily, M, trials=100)\n",
    "dataGood = getCollisionProbabilities(drawFromGoodHashFamily, M, trials=100)\n",
    "#dataGreat = getCollisionProbabilities(drawFromBestHashFamily, M, trials=100)\n",
    "# As we saw before, this last one takes a really long time!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "counts, bins, patchs = plt.hist([dataBad,dataGood], color=[\"orange\",\"blue\"], label=[\"not good hash family\", \"universal hash family\"], bins=10)\n",
    "plt.legend()\n",
    "plt.xticks(bins)\n",
    "plt.xlabel(\"Probability of collision\")\n",
    "plt.ylabel(\"Number of pairs of elements\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
